package DataStructrue;
//前缀,差分
public class PreDif {
    static long[] a={5,2,6,4,1,3};//原数组支持单点查询与修改

    //一维差分数组,支持单点与区间修改
    public static long[] dif(long[] a){
        long[] dif=new long[a.length];
        for (int i = 0; i < dif.length; i++) {
            if(i==0) dif[i]=a[i];
            else dif[i]=a[i]-a[i-1];
        }
        return dif;
    }
    //一维前缀数组,支持单点与区间查询
    public static long[] pre(long[] a){
        long[] pre=new long[a.length];
        for (int i = 0; i < pre.length; i++) {
            if(i==0) pre[i]=a[i];
            else pre[i]=a[i]+pre[i-1];
        }
        return pre;
    }
    //二维差分数组
    public static long[][] dif2(long[][] a){
        long[][] dif=new long[a.length][a[0].length];
        //处理边界
        for (int i = 1; i < dif.length; i++) {
            dif[0][i]-=a[0][i-1];
        }
        for (int i = 1; i < dif[0].length; i++) {
            dif[i][0]-=a[i-1][0];
        }
        for (int i = 1; i < dif.length; i++) {
            for (int j = 1; j < dif[0].length; j++) {
                dif[i][j]-=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
            }
        }
        return dif;
    }
    //二维前缀数组
    public static long[][] pre2(long[][] a){
        long[][] pre=new long[a.length][a[0].length];
        for (int i = 1; i < pre.length; i++) {
            pre[0][i]+=a[0][i-1];
        }
        for (int i = 1; i < pre[0].length; i++) {
            pre[i][0]+=a[i-1][0];
        }
        for (int i = 1; i < pre.length; i++) {
            for (int j = 1; j < pre[0].length; j++) {
                pre[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
            }
        }
        return pre;
    }
}
